AWC0077 E - プレゼント配布
Difficulty:None
問題
N人の参加者がいる。プレゼントがM種類ある。各プレゼントは$ C_i個用意されている。
それぞれの参加者には「このプレゼントのどれかがほしい」といった希望がある。各参加者はプレゼントを1つまで得ることができる。最大で何人の希望をかなえられるか。
解法
頂点を$ N+M+2 個用意する。
$ A_i(0 \le i<N)：$ i番目の生徒を表す。
$ B_i(0 \le i< M)：$ i番目の席を表す。
$ S：フローの始点。
$ T：フローの終点。
以下のような条件で辺を張る。
$ i番目の参加者が$ j番目のプレゼントを希望しているとき、$ A_iから$ B_jに容量1の辺を張る。
$ Sから$ A_i(0 \le i<N)に容量1の辺を貼る。これは各参加者が高々1つのプレゼントを受けとることができることを表す。
$ B_i(0 \le i< M)から$ Tに容量$ C_iの辺を貼る。これはそれぞれのプレゼントが$ C_i個あることを表す。
$ Sから$ Tまでの最大フローが答えとなる。
実装
code:cpp
using namespace std;
using namespace atcoder;
int main(){
int n,m;
cin >> n >> m;
vector<int>b(m);
for(auto&i:b)cin >> i;
vector<vector<int>>s;
for(int i = 0;i<n;i++){
int k;cin >> k;
vector<int>tmp(k);
for(int j = 0;j<k;j++)cin>>tmpj; s.push_back(tmp);
}
mf_graph<int>g(n+m+2);
int S = n+m,T = n+m+1;
for(int i = 0;i<n;i++){
g.add_edge(i,j+n-1,1);
}
g.add_edge(S,i,1);
}
for(int i = 0;i<m;i++)g.add_edge(i+n,T,bi); cout << g.flow(S,T) << endl;
}